package com.richpay.basejava.base14;

/**
 * 二分法查找
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] intArray = {7, 8, 10, 15, 23};
        //int dest = 23;
        int dest=100;
        int index = binarySearch(intArray, dest);
        System.out.println("index=" + index);

        if (index != -1) {
            System.out.println("数据" + dest + "存在于数组intArray[" + index + "]处。");
        } else {
            System.out.println("数据" + dest + "不存在数组intArray中!");
        }

    }

    /**
     * 二分法查找的前提是：数组中的元素必须是有序的。
     * @param array
     * @param num
     * @return
     */
    static int binarySearch(int[] array, int num) {
        int lower = 0;
        int upper = array.length - 1;
        while (lower <= upper) {
            int mid = (lower + upper) / 2;
            if (array[mid] > num) {
                upper = mid - 1;
            } else if (array[mid] < num) {
                lower = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}
